/// @tags: Matrix Floyd
#include <cstdio>
#include <cstring>
#include <iostream>
#define rint register int

using std::cin;
using std::cout;
using std::min;

namespace BlueQuantum {

constexpr int MAXN = 2e2 + 3, INF = 0x3f3f3f3f;

struct Matrix {
  static int n;
  int a[MAXN][MAXN];

  inline Matrix() { memset(a, INF, sizeof(a)); }

  inline int *operator[](int index) { return a[index]; }
  inline const int *operator[](int index) const { return a[index]; }

  inline Matrix operator*(const Matrix &rhs) const {
    Matrix res;
    for (rint k = 1; k <= n; ++k)
      for (rint i = 1; i <= n; ++i)
        for (rint j = 1; j <= n; ++j) res[i][j] = min(res[i][j], a[i][k] + rhs[k][j]);
    return res;
  }

  inline Matrix operator^(int exp) const {
    Matrix res, base(*this);
    for (int i = 1; i <= n; ++i) res[i][i] = 0;
    for (; exp; exp >>= 1, base = base * base)
      if (exp & 1) res = res * base;
    return res;
  }
} A;

int Matrix::n, dcnt;
int disc[1003];

inline int main() {
  int n, t, s, e;
  cin >> n >> t >> s >> e;
  for (rint i = 1; i <= t; ++i) {
    int w, u, v;
    cin >> w >> u >> v;
    if (disc[u] == 0) disc[u] = ++dcnt;
    if (disc[v] == 0) disc[v] = ++dcnt;
    A[disc[u]][disc[v]] = w;
    A[disc[v]][disc[u]] = w;
  }
  Matrix::n = dcnt;
  cout << (A ^ n)[disc[s]][disc[e]];
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P2886 [USACO07NOV] Cow Relays G.in", "r", stdin);
  freopen("P2886 [USACO07NOV] Cow Relays G.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
